package com.sx.sx1.lintcode.day717;

import java.util.LinkedList;

public class LC849 {

    static class Solution {
        /**
         * @param s: the expression string
         * @return: the answer
         */
        public int calculate(String s) {
            return f(s, 0)[0];
        }

        public int[] f(String s, int i) { //返回int[2]: 0:当前结方法结果的val  1:来到当前到字符串的x位置
            LinkedList<String> ll = new LinkedList<>();
            int cur = 0;
            int[] info = {0, 0};

            while (i < s.length() && s.charAt(i) != ')') {
                char chs = s.charAt(i);
                if (chs == ' ') {
                    i++;
                    continue;
                }

                if (chs >= '0' && chs <= '9') {
                    cur = cur * 10 + (chs - '0');
                    i++;
                } else if (chs != '(') { //遇到运算符了
                    addNum(ll, cur);
                    ll.add(String.valueOf(chs));
                    i++;
                    cur =0;
                }else{
                    info = f(s,i+1);
                    i= info[1]+1;
                    cur = info[0];
                }
            }

            addNum(ll,cur);
            info[0] = addRes(ll);
            info[1] = i;
            return info;
        }


        public int addRes(LinkedList<String> ll){
            int res =0;
            boolean add = true;
            String cur;
            while (!ll.isEmpty()){
                cur = ll.pollFirst();
                if(cur.equals("+")) add =true;
                else if(cur.equals("-")) add= false;
                else{
                    int k = Integer.valueOf(cur);
                    if(add) res+=k;
                    else res-=k;
                }
            }
            return res;
        }
        public void addNum(LinkedList<String> ll, int num) {
            if(!ll.isEmpty()){
                String top = ll.peekLast();
                if(top.equals("*")){
                    ll.pollLast();
                    int cur = Integer.valueOf(ll.pollLast());
                    num = cur*num;
                }

                if(top.equals("/")){
                    ll.pollLast();
                    int cur = Integer.valueOf(ll.pollLast());
                    num = cur/num;
                }
            }
            ll.add(String.valueOf(num));
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.calculate("1 + 1"));
        System.out.println(obj.calculate(" 6-4 / 2 "));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
849 · 基础计算器 III
算法
困难
通过率
48%

题目
题解25
笔记
讨论49
排名
记录
描述
实现一个基本的计算器来计算一个简单的表达式字符串。

表达式字符串只包含非负整数、+, -, *, /操作符、左括号 (，右括号 )和空格。

您可以假设给定的表达式总是有效的。所有中间结果将在“[-2147483648,2147483647]”范围内。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


不要使用eval内置的库函数。

样例
样例 1:

输入："1 + 1"
输出：2
解释：1 + 1 = 2
样例 2:

输入：" 6-4 / 2 "
输出：4
解释：4/2=2，6-2=4
标签
企业
Microsoft
相关题目

978
基础计算器
中等

980
基础计算器 II
中等

981
基础计算器 IV
困难
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
已开启智能提示
发起考试
45 分 00 秒
123456789
public class Solution {
    /**
     * @param s: the expression string
     * @return: the answer

public int calculate(String s) {
    // Write your code here
}
}
控制台
        历史提交

 */